//
// Created by Administrator on 2021/11/10.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
// 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

//请你重新构造并返回输入数组people 所表示的队列。
// 返回的队列应该格式化为数组 queue ，
// 其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。


//我们在初始时建立一个包含 n 个位置的空队列，而我们每次将一个人放入队列中时，会
// 将一个「空」位置变成「满」位置，那么当我们放入第 i 个人时，我们需要给他安排一个「空」位置，
// 并且这个「空」位置前面恰好还有 k_i个「空」位置，用来安排给后面身高更高的人。
// 也就是说，第 i 个人的位置，就是队列中从左往右数第 k_i+1个「空」位置。

class Solution {
public:
    /**
     * 从低到高考虑
     * 给后面身高更高的人准备空位
     * @param people
     * @return
     */
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
        // 按身高排序，身高相同，按照位置从大到小排序
        sort(people.begin(), people.end(), [](vector<int> &a, vector<int> &b) {
            return a[0] < b[0] or (a[0] == b[0] and a[1] > b[1]);
        });
        unsigned int n = people.size();
        vector<vector<int>> ans(n);
        for (const vector<int> &person:people) {
            int spaces = person[1] + 1; // 这个人所处的空位置序号
            for (int i = 0; i < n; ++i) {
                if (ans[i].empty()) {
                    --spaces;
                    if (!spaces) {
                        ans[i] = person;
                        break;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * 从高到低考虑
     * 对于第i个，前面的都有影响，后面的没有影响
     * 直接去找当前序列中自己的位置 因为它的插入对于之前的人没影响
     * @param people
     * @return
     */
    vector<vector<int>> reconstructQueue2(vector<vector<int>> &people) {
        // 身高降序，位置升序
        sort(people.begin(), people.end(), [](const vector<int> &u, const vector<int> &v) {
            return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]);
        });
        vector<vector<int>> ans;
        // 插入到对应位置，前面的都比它大  插入操作不太好
        for (const vector<int> &person: people) {
            ans.insert(ans.begin() + person[1], person);
        }
        return ans;
    }


};

int main() {
    vector<vector<int>> people{{7, 0},
                               {4, 4},
                               {7, 1},
                               {5, 0},
                               {6, 1},
                               {5, 2}};
    Solution solution;
    auto ans = solution.reconstructQueue(people);
    for (const auto &row:ans) {
        for (const auto &x:row) {
            cout << x << " ";
        }
        cout << endl;
    }
    return 0;
}


